package com.hy;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:链表单调栈
 * author: Mr.Du
 * Date: 2024/1/3
 * Time: 11:25
 */
public class MonotonicStackExample {

    public static ListNode removeNodes(ListNode head){
        List<Integer> list = new ArrayList<>();
        while(head != null){
            list.add(head.val);
            head = head.next;
        }
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[list.size()];
        for(int i = list.size() - 1;i >= 0;i--){
            while(!stack.isEmpty() && stack.peek() <= list.get(i)){
                stack.pop();
            }
            res[i] = stack.isEmpty()? -1 : stack.peek();
            stack.push(list.get(i));
        }
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        for(int i = 0;i < list.size();i++){
            if(res[i] == -1){
                cur.next = new ListNode(list.get(i));
                cur = cur.next;
            }
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        // 示例链表: 2 -> 1 -> 5 -> 4 -> 3
        ListNode head = new ListNode(2);
        head.next = new ListNode(1);
        head.next.next = new ListNode(5);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(3);

        head = removeNodes(head);
        System.out.println("Next Larger Nodes:");
        while(head != null){
            System.out.print(head.val + " ");
            head = head.next;
        }

    }
}
